package Day2025_03_07;

import java.util.LinkedList;
import java.util.Queue;

class Pair<K, V> {
    private K key;
    private V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    public K getKey() {
        return key;
    }
    public V getValue() {
        return value;
    }
}

public class LeetCode733 {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int n1 = image.length;
        int n2 = image[0].length;
        int prev = image[sr][sc];
        if (prev == color) return image;
        Queue<Pair<Integer, Integer>> q = new LinkedList<>();
        q.add(new Pair(sr, sc));
        while (!q.isEmpty()) {
            Pair<Integer, Integer> ret = q.poll();
            int a = ret.getKey(), b = ret.getValue();
            image[a][b] = color;
            for (int i = 0; i < 4; i++) {
                int m = a + dx[i], n = b + dy[i];
                if (m >= 0 && m < n1 && n >=0 && n < n2 && image[m][n] == prev) {
                    q.add(new Pair(m, n));
                }
            }
        }
        return image;
    }

    public static void main(String[] args) {
        LeetCode733 leetCode733 = new LeetCode733();
        int[][] image = {{0, 0, 0},{0, 0, 0}};
        int sr = 0, sc = 0, color = 0;
        int[][] ret = leetCode733.floodFill(image, sr, sc, color);
        for (int i = 0; i < ret.length; i++) {
            for (int j = 0; j < ret[0].length; j++) {
                System.out.print(ret[i][j] + " ");
            }
            System.out.println();
        }
    }
}
